A duality theoretic perspective on recognisable languages
Date
2019-04
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Stellenbosch : Stellenbosch University
Abstract
ENGLISH ABSTRACT : A connection between recognisable languages and profinite identities is
established through the composition of two famous theorems: Eilenberg’s theorem and Reiterman’s theorem. In this work, we present a detailed account of
the duality-theoretic approach by Gehrke et al. that has been shown to bridge
the gap and demonstrate that Eilenberg’s varieties and profinite theories are
directly linked: they are at opposite ends of an extended Stone-type duality,
instantiating a Galois correspondence between subobjects and quotients and
resulting in an equational theory of recognisable languages. We give an indepth overview of relevant components of algebraic language theory and the
profinite equational theory of pseudovarieties in order to show how they are
tied together by the duality-theoretic developments. Furthermore, we provide
independent proofs of the key Galois connections at the heart of these bridging
results.
AFRIKAANSE OPSOMMING : Geen Afrikaanse opsomming geskikbaar nie
AFRIKAANSE OPSOMMING : Geen Afrikaanse opsomming geskikbaar nie
Description
Thesis (MSc)--Stellenbosch University, 2019.
Keywords
Boolean algebras, Formal language theory, Duality theory (Mathematics), Lattices, Stone duality (Mathematics), UCTD